import java.util.Collection;
import java.util.LinkedList;

/**
 * An abstract class whose only purpose in life is to run Kruskal's algorithm.
 * 
 * @author BaoTam
 * 
 */
public abstract class MST {

	/**
	 * Run kruskal's algorithm on the given EdgeList and return a collection of
	 * edges.
	 * 
	 * @param edges
	 * @return
	 */
	public static Collection<Edge> kruskal(EdgeList edges) {
		Collection<Edge> result = new LinkedList<Edge>();
		if(edges == null) {
			return null;
		}
		DisjointSets disjSets = new DisjointSets(edges.getVertices());
		for(Edge edge : edges) {
			System.out.print("current: " + edge);
			if(!disjSets.sameSet(edge.vertices()[0], edge.vertices()[1])) {
				System.out.print("  ->add");
				result.add(edge);
				disjSets.merge(edge.vertices()[0], edge.vertices()[1]);
			}
			System.out.println();
		}
		return result;
	}
	
	/**
	 * main method for debugging purpose
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(MST.kruskal(new EdgeList("14 1 2 1 1 3 3 3 2 3 2 5 6 4 5 5 3 4 7 5 6 9 5 7 11 6 7 2 4 6 8 4 8 8 8 9 10 8 1 9 9 1 12")));
	}

}
